package 代码随想2._3哈希表;

/**
 * @author XXX
 * @date 2024-01-14 16:03
 */

import java.util.*;

/**
 * https://leetcode.cn/problems/valid-anagram/
 */

class Test{
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);

        for(int i=0 ; i<nums.length; i++){
            if(nums[i]>0 && nums[i] > target)
                return result;
            if(i>0 && nums[i] == nums[i-1])
                continue;

            for(int j=i+1; j<nums.length;j++){
                if(j>i+1 && nums[j-1] == nums[j])
                    continue;
                int left = j+1;
                int right = nums.length - 1;
                while (right > left){
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if(sum > target)
                        right--;
                    else if(sum < target)
                        left++;
                    else {
                        result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));

                        while (left<right && nums[right] == nums[right-1]) right--;
                        while (left < right && nums[left] == nums[left+1]) left++;

                        right--;
                        left++;
                    }
                }
            }
        }
        return result;
    }
}

public class _1有效的字母异位词 {
    public boolean isAnagram(String s, String t) {
        HashMap<Character,Integer> res = new HashMap<>();
        for(int i=0; i<s.length();i++){
            res.put(s.charAt(i),res.getOrDefault(s.charAt(i),0)+1);
        }
        for(int i=0; i<t.length(); i++){
            if(!res.containsKey(t.charAt(i)))
                return false;
            else{
                res.put(t.charAt(i),res.get(t.charAt(i) )- 1);
                if(res.get(t.charAt(i))==0)
                    res.remove(t.charAt(i));
            }
        }
        if(res.isEmpty())
            return true;
        else
            return false;
    }

    public boolean isAnagram2(String s, String t) {
        //字典解法   时间复杂度O(m+n) 空间复杂度O(1)
        int[] record = new int[26];
        for (int i = 0; i < s.length(); i++) {
            record[s.charAt(i) - 'a']++;     // 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
        }
        for (int i = 0; i < t.length(); i++) {
            record[t.charAt(i) - 'a']--;
        }
        for (int count: record) {
            if (count != 0) {               // record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
                return false;
            }
        }
        return true;                        // record数组所有元素都为零0，说明字符串s和t是字母异位词
    }
}

/**
 * https://leetcode.cn/problems/ransom-note/
 */
class 赎金信{
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] dic = new int[26];
        for(int i=0; i<magazine.length();i++)
            dic[magazine.charAt(i) - 'a']++;
        for(int i=0; i<ransomNote.length();i++){
            dic[ransomNote.charAt(i)-'a']--;
            if(dic[ransomNote.charAt(i)-'a']<0)
                return false;
        }
        return true;
    }
}

/**
 * https://leetcode.cn/problems/group-anagrams/description/
 */
class 字母异位词分组{
    //排序
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }

        return new ArrayList<List<String>>(map.values());
    }

    //计数
    public List<List<String>> groupAnagrams2(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            int[] counts = new int[26];
            int length = str.length();
            for (int i = 0; i < length; i++) {
                counts[str.charAt(i) - 'a']++;
            }
            // 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < 26; i++) {
                if (counts[i] != 0) {
                    sb.append((char) ('a' + i));
                    sb.append(counts[i]);
                }
            }
            String key = sb.toString();
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

/**
 * https://leetcode.cn/problems/find-all-anagrams-in-a-string/
 */
class 找到字符串中所有字母异位词{
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();
        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }

        List<Integer> ans = new ArrayList<Integer>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];

        for (int i = 0; i < pLen; ++i) {
            ++sCount[s.charAt(i) - 'a'];
            ++pCount[p.charAt(i) - 'a'];
        }
        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }

        for (int i = 0; i < sLen - pLen; ++i) {
            --sCount[s.charAt(i) - 'a'];
            ++sCount[s.charAt(i + pLen) - 'a'];

            if (Arrays.equals(sCount, pCount)) {
                ans.add(i + 1);
            }
        }

        return ans;
    }
}